#include <stdio.h>

void swap(int* a1, int* a2)
{
    int tmp = *a1;
    *a1 = *a2;
    *a2 = tmp;
}

void sort(int* array, int nCnt)
{
    int nRight = 0;
    int nLeft = 0;
    int nMid = 0;
    int nTmp = 0;

    for (int i = 1; i < nCnt; i++)
    {
        if (i == 1)
        {
            if (array[i] < array[i - 1]) 
                swap(&array[i], &array[i - 1]);
        }

        nRight = i - 1;
        nLeft = 0;

        if (array[i] > array[nRight]) continue;

        while (nRight >= nLeft)
        {
            nMid = (nRight + nLeft) / 2;

            if (array[nMid] < array[i])
                nLeft = nMid + 1;
            else
                nRight = nMid - 1;
        }

        nTmp = array[i];
        for (int k = i; k > nRight + 1; k--)
            array[k] = array[k - 1];

        array[nRight + 1] = nTmp;
    }
}

int main()
{
    int array[9] = { 2,8,5,1,3,11,7,2,6 };

    sort(array, sizeof(array) / sizeof(int));

    for (unsigned int i = 0; i < (sizeof(array) / sizeof(int)); ++i)
        printf("%d ", array[i]);
    puts("");

    return 0;
}